{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3.2 Standard notations and common functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2-1\n",
    "\n",
    "> Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n) + g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n) \\cdot g(n)$ is monotonically increasing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $f(n) + g(n)$\n",
    "\n",
    "$n \\le m$\n",
    "\n",
    "$f(n) \\le f(m)$ and $g(n) \\le g(m)$\n",
    "\n",
    "$f(n) + g(n) \\le f(m) + g(m)$\n",
    "\n",
    "* $f(g(n))$\n",
    "\n",
    "$n \\le m$\n",
    "\n",
    "$f(n) \\le f(m)$\n",
    "\n",
    "$g(f(n)) \\le g(f(m))$\n",
    "\n",
    "* $f(n) \\cdot g(n)$\n",
    "\n",
    "$n \\le m$\n",
    "\n",
    "$f(n) \\le f(m)$ and $g(n) \\le g(m)$\n",
    "\n",
    "$f(n) \\cdot g(n) \\le f(m) \\cdot g(m)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2-2\n",
    "\n",
    "> Prove equation (3.16).\n",
    ">\n",
    "> $a^{log_bc}=c^{log_ba}$ (3.16)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$a^{log_bc}=a^{\\frac{log_ac}{log_ab}}=c^{\\frac{1}{log_ab}}=c^{log_ba}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2-3\n",
    "\n",
    "> Prove equation (3.19). Also prove that $n! = \\omega(2^n)$ and $n!=o(n^n)$.\n",
    ">\n",
    "> $\\lg(n!)=\\Theta(n \\lg n)$ (3.19)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $\\lg(n!)=\\Theta(n \\lg n)$\n",
    "\n",
    "Use Stirling's approximation:\n",
    "\n",
    "$\\lg(n!) = \\lg(\\sqrt{2 \\pi n}\\left (\\frac{n}{e}\\right )^n e^{\\alpha n})$ $=\\lg(\\sqrt{2 \\pi n}) + \\lg(\\left (\\frac{n}{e}\\right )^n) + \\lg (e^{\\alpha n})$ $=\\Theta(\\lg \\sqrt{n}) + \\Theta(n\\lg n) + \\Theta(n)$ $=\\Theta(n\\lg n)$\n",
    "\n",
    "* $n! = \\omega(2^n)$\n",
    "\n",
    "$n!=n \\cdot (n-1) \\cdot \\cdots \\cdot 1 \\ge 4 \\cdot 2 \\cdot \\cdots \\cdot 2 \\cdot 1 = 2^n$\n",
    "\n",
    "* $n!=o(n^n)$\n",
    "\n",
    "$n!=n \\cdot (n-1) \\cdot \\cdots \\cdot 1 \\le n \\cdot n \\cdot \\cdots \\cdot n = n^n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2-4 $\\star$\n",
    "\n",
    "> Is the function $\\left \\lceil \\lg n \\right \\rceil!$ polynomially bounded? Is the function $\\left \\lceil \\lg \\lg n \\right \\rceil!$ polynomially bounded?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $\\left \\lceil \\lg n \\right \\rceil!$\n",
    "\n",
    "$\\left \\lceil \\lg n \\right \\rceil!$ $= \\sqrt{2 \\pi \\lg n}\\left (\\frac{\\lg n}{e}\\right )^{\\lg n} e^{\\alpha \\lg n}$ $= \\Theta((\\lg n)^{\\lg n})$\n",
    "\n",
    "$\\lg \\left \\lceil \\lg n \\right \\rceil!$ $= \\Theta(\\lg n \\lg \\lg n)$\n",
    "\n",
    "$\\lg n^p$ $=\\Theta(\\lg n)$\n",
    "\n",
    "$\\Theta(\\lg n \\lg \\lg n) > \\Theta(\\lg n)$\n",
    "\n",
    "$\\therefore$ not bounded.\n",
    "\n",
    "* $\\left \\lceil \\lg \\lg n \\right \\rceil!$\n",
    "\n",
    "$\\left \\lceil \\lg \\lg n \\right \\rceil!$ $= \\Theta((\\lg\\lg n)^{\\lg \\lg n})$\n",
    "\n",
    "$\\lg \\left \\lceil \\lg \\lg n \\right \\rceil!$ $= \\Theta(\\lg \\lg n \\lg \\lg \\lg n)$ $=o(\\lg^2\\lg n)$\n",
    "\n",
    "$\\because$ $\\lg^bn=o(n^a)$\n",
    "\n",
    "$\\therefore$ $o(\\lg^2\\lg n)$ $=o(\\lg n)$, is polynomially bounded."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2-5 $\\star$\n",
    "\n",
    "> Which is asymptotically larger: $\\lg (\\lg^{\\ast}n)$ or $\\lg^{\\ast}(\\lg n)$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\lg (\\lg^{\\ast} (2^m))$ and $\\lg^{\\ast}(\\lg (2^m))$\n",
    "\n",
    "$\\lg (1 + \\lg^{\\ast}m)$ and $\\lg^{\\ast}m$\n",
    "\n",
    "$\\because$ $\\lg (x)$ < $x$\n",
    "\n",
    "$\\therefore$ The right hand side is larger."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2-6\n",
    "\n",
    "> Show that the golden ratio $\\phi$ and its conjugate $\\hat{\\phi}$ both satisfy the equation $x^2=x+1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\phi = \\frac{1 + \\sqrt{5}}{2}$\n",
    "\n",
    "$\\phi^2=\\frac{6+2\\sqrt{5}}{4}=\\frac{1 + \\sqrt{5}}{2} + 1 = \\phi + 1$\n",
    "\n",
    "$\\hat{\\phi} = \\frac{1 - \\sqrt{5}}{2}$\n",
    "\n",
    "$\\hat{\\phi}^2=\\frac{6-2\\sqrt{5}}{4}=\\frac{1 - \\sqrt{5}}{2} + 1 = \\hat{\\phi} + 1$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2-7\n",
    "\n",
    "> Prove by induction that the $i$th Fibonacci number satisfies the equality\n",
    ">\n",
    "> $$\n",
    "F_i=\\frac{\\phi^{i}-\\hat{\\phi^i}}{\\sqrt{5}}\n",
    "$$\n",
    ">\n",
    "> where $\\phi$ is the golden ratio and $\\hat{\\phi}$ is its conjugate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$F_0=0$, $\\frac{\\phi^{0}-\\hat{\\phi^0}}{\\sqrt{5}}=0$\n",
    "\n",
    "$F_1=1$, $\\frac{\\phi-\\hat{\\phi}}{\\sqrt{5}}=1$\n",
    "\n",
    "Suppose $F_{i-2}=\\frac{\\phi^{i-2}-\\hat{\\phi^{i-2}}}{\\sqrt{5}}$ and $F_{i-1}=\\frac{\\phi^{i-1}-\\hat{\\phi^{i-1}}}{\\sqrt{5}}$,\n",
    "\n",
    "$F_i=F_{i-2}+F_{i-1}=\\frac{1}{\\sqrt{5}}(\\phi^{i-2}-\\hat{\\phi^{i-2}} + \\phi^{i-1}-\\hat{\\phi^{i-1}})$\n",
    "\n",
    "Based on the previous exercise,\n",
    "\n",
    "$\\phi^{i-2} + \\phi^{i-1} = \\phi^{i-2}(1+\\phi) = \\phi^{i-2}\\phi^2 = \\phi ^ i$\n",
    "\n",
    "$\\therefore$ $F_i=\\frac{\\phi^{i}-\\hat{\\phi^i}}{\\sqrt{5}}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2-8\n",
    "\n",
    "> Show that $k \\ln k = \\Theta(n)$ implies $k = \\Theta(n / \\ln n)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$c_1n \\le k \\ln k \\le c_2n$\n",
    "\n",
    "$\\ln (c_1n) \\le \\ln(k \\ln k) \\le \\ln (c_2n)$\n",
    "\n",
    "$\\ln c_1 + \\ln n \\le \\ln k + \\ln \\ln k \\le \\ln c_2 + \\ln n$\n",
    "\n",
    "$\\because$ $\\ln k + \\ln \\ln k \\le 2\\ln k \\ge \\ln c_1 + \\ln n$\n",
    "\n",
    "$\\therefore$ $\\frac{\\ln k}{\\ln n} \\ge \\frac{1}{2}$\n",
    "\n",
    "$\\because$ $\\ln k + \\ln \\ln k \\ge \\ln k \\le \\ln c_2 + \\ln n$\n",
    "\n",
    "$\\therefore$ $\\frac{\\ln k}{\\ln n} \\le 1$\n",
    "\n",
    "$\\because$ $c_1n \\le k \\ln k \\le c_2n$\n",
    "\n",
    "$\\therefore$ $\\frac{c_1 n}{\\ln n} \\le \\frac{k \\ln k}{\\ln n} \\le \\frac{c_2 n}{\\ln n}$\n",
    "\n",
    "$\\therefore$ $\\frac{c_1 n}{\\ln n} \\le \\frac{k \\ln k}{\\ln n} \\le k$ and $\\frac{c_2 n}{\\ln n} \\ge \\frac{k \\ln k}{\\ln n} \\ge \\frac{1}{2}k$\n",
    "\n",
    "$\\therefore$ $c_1\\frac{n}{\\ln n} \\le k \\le (2c_2)\\frac{n}{\\ln n}$\n",
    "\n",
    "$\\therefore$ $k = \\Theta(n / \\ln n)$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
